\section{Preliminaries}

This section introduces the most important definitions of two-dimensional languages. The notions are mainly from~\cite{giammarresi1997twodimensional} and~\cite{cherubini2009picture}. We assume that the reader is already familiar with basic notions of the one-dimensional formal language theory.

\begin{definition}
	Let $\Sigma$ be a finite, non-empty set of characters. Then p is a picture over $\Sigma$, if p is a rectangular array containing only symbols of $\Sigma$. The set of all pictures over $\Sigma$ is denoted by $\Sigma^{*,*}$.
\end{definition}

Let $p$ be a picture. The height and the width of the picture are denoted as $l_1(p)$ and $l_2(p)$, respectively. The size of the picture is the pair $(l_1(p), l_2(p))$. There is only one picture of size $(0, 0)$. This picture is called empty picture and is denoted as $\lambda$. The set $\Sigma^{h, k} \subset \Sigma^{*, *}$ denotes the set of pictures over $\Sigma$ of size $(h, k)$. 

Sometimes it is necessary that a picture is surrounded by a special symbol to detect whether a border of the picture has been reached. For this purpose, we use the symbol $\#$ and with $\hat{p}$ we denote the picture $p$, bordered with $\#$'s:

\begin{center}
	$\hat{p} =$ \begin{tabular}{|ccccc|}
		\hline
		\#       & \#        & \dots    & \#        & \#		\\
		\#       & $p(1, 1)$   & \dots    & $p(1, n)$   & \#		\\
		$\vdots$ & $\vdots$  & $\ddots$ & $\vdots$  & $\vdots$	\\
		\#       & $p(m, 1)$   & \dots    & $p(m, n)$   & \#		\\
		\#       & \#        & \dots    & \#        & \#		\\
		\hline
	\end{tabular}
\end{center}

If we need the value of one specific pixel within the picture, we use $p(i, j)$ to return the symbol in the picture $p$, at the vertical position $i$, and horizontal position $j$, where $1 \leq i \leq l_1(p)$ and $1 \leq j \leq l_2(p)$. The set of all positions of a picture of size $(m, n)$ is denoted as $P(m, n) = \{1, \dots, m\} \times \{1, \dots, n\}$. The set of all positions of a bordered picture of size $(m, n)$ is denoted by $\hat{P}(m, n) = \{0, \dots, m + 1\} \times \{0, \dots, n + 1\}$. 

\begin{definition}
	Let $p \in \Sigma^{*,*}$ be a picture of size $(m, n)$.
	$q = p((i, j), (i', j'))$ is called a subpicture of p when
	$1 \leq i \leq i' \leq l_1(p)$ and $1 \leq j \leq j' \leq l_2(p)$
	satisfying the following conditions:
	\begin{compactitem}
	  \item $l_1(q) = i' - i + 1 \text{ and } l_2(q) = j' - j + 1$,
	  \item
	  $\forall k, r (1 \leq k \leq l_1(q) \text{ and } 1 \leq r \leq l_2(q))$ is $q(k, r) = p(k + i - 1, r + j - 1)$
	\end{compactitem}
\end{definition}

For any $p \in \Sigma^{*,*}$, the $i$-th row $p((i, 1), (i, l_2(x)))$ of $p$ is
simply denoted by $p(i, *)$ and the $j$-th column by $p(*, j)$. Sometimes it is necessary to look at all subpictures of a picture p.
Therefore, we denote the set of subpictures of size $(h, k)$ as \[B_{h, k}(p) = \{q \in \Sigma^{*,*} \mid l_1(q) = h, l_2(q) = k \text{ and $q$ is a subpicture of $p$}\}.\]
The concatenation of pictures can be done in two directions: horizontally and vertically. Two pictures $p, q \in \Sigma^{*,*}$ can be horizontally concatenated, if $l_1(p) = l_1(q)$. We denote the horizontal concatenation by $p \hcat{} q$.  Similarly, two pictures can be concatenated vertically, if $l_2(p) = l_2(q)$. We then write $p \vcat{} q$. Moreover, the empty picture $\lambda$ can always be concatenated and is the neutral element for both of the concatenation operations. 

\begin{definition}
	Let $L_1, L_2 \in \Sigma^{*,*}$ be two two-dimensional languages. The horizontal concatenation is defined by \[L_1 \hcat{} L_2 = \{p \hcat{} q \mid p \in L_1, q \in L_2\}\]
\end{definition}

Similarly, the vertical concatenation of two-dimensional languages is defined. 

As well known from string languages, we can define a sort of two-dimensional Kleene star for the horizontal (or vertical) concatenation closure of L. 

\begin{definition}
	Let $L \in \Sigma^{*,*}$ be a two-dimensional language. The horizontal closure is defined by \[L^{*\hcat} = \underset{i \geq 0}{\bigcup} L^{i \hcat} \text{ with } L^{0 \hcat} = \{\lambda\}, L^{n \hcat} = L \hcat L^{(n-1) \hcat}\]
\end{definition}

Similarly, the vertical concatenation closure of two-dimensional languages is defined. 

Some later definitions will work with projections of pictures and languages. Therefore we need the definition of the projection by mapping: 

\begin{definition}
	Let $\Gamma$ and $\Sigma$ be two finite alphabets and $\pi: \Gamma \rightarrow \Sigma$ be a mapping. Let $p \in \Gamma^{*,*}$ be a picture of size $(m, n)$. $q \in \Sigma^{*,*}$ is a projection of $p$, if q has the size $(m, n)$ and $q(i, j) = \pi(p(i, j))$ for all $1 \leq i \leq m$ and $1 \leq j \leq n$. We write $q = \pi(p)$. 
\end{definition}

Since the projection is not required to be injective, a picture can have more than one preimage. We receive the projection of a language $L$ as $L' = \pi(L) = \{q \mid q = \pi(p), p \in L\}$

Another operation on pictures is rotating. 

\begin{definition}
	Let $p \in \Sigma^{*, *}$ be a picture. The clockwise rotated picture $p^R$ is 
	
	\begin{center}
		$p^R = $ \begin{tabular}{|ccc|}
			\hline
			$p(m, 1)$   & \dots    & $p(1, 1)$   \\
			$\vdots$  & $\ddots$ & $\vdots$  \\
			$p(m, n)$   & \dots    & $p(1, n)$   \\
			\hline
		\end{tabular}
	\end{center}
\end{definition}

Counterclockwise rotation can be defined similarly. With this operator, it is possible to define the rotation of a language $L$ by $L^R = \{p^R \mid p \in L\}$. Based on this idea, it is possible to define horizontal and vertical mirroring of pictures and languages.

The last operation on pictures is the row and column cyclic closure. This
definition is taken from~\cite{ito1997nonclosure}.

\begin{definition}
	Let $p \in \Sigma^{*,*}$ be a picture of size $(m, n)$. A row cyclic closure
	$p^{RC}$ of $p$ is a two-dimensional tape $q$ with the same size as $p$ and
	satisfying \[q(i, j) = p(((i + k - 1) \text{ mod } m) + 1, j)\] for each
	$i, j (1 \leq i \leq m, 1 \leq j \leq n)$ and for some integer
	$k (1 \leq k \leq m)$. The row cyclic closure picture $p^{RC}$ for some integer
	$k (1 \leq k \leq m)$ is
	\begin{center}
	$p^{RC} = $\begin{tabular}{|ccc|}
		\hline
		$p(k + 1, 1)$ & \dots    & $p(k + 1, n)$ \\
		$\vdots$      & $\ddots$ & $\vdots$      \\
		$p(m, 1)$     & \dots    & $p(m, n)$     \\
		$p(1, 1)$     & \dots    & $p(1, n)$     \\
		$\vdots$      & $\ddots$ & $\vdots$      \\
		$p(k, 1)$     & \dots    & $p(k, n)$     \\
		\hline
	\end{tabular}
\end{center}
\end{definition} 